package com.fengdi.solutions.middle;


import java.util.*;

/**
 * @author FengDi
 * @Description 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 * @Solution 用映射表记录数字的出现次数，找出出现次数超过⌊ n/3 ⌋次的元素
 * */
public class _229_multiple_elements {
    private Map<Integer, Integer> map = new HashMap<>();

    public List<Integer> majorityElement(int[] nums) {
        final List<Integer> result = new ArrayList<Integer>();
        int n = nums.length / 3;
        Arrays.sort(nums); // 将数组排序
        // 创建映射表
        for (int num : nums) {
            if (this.map.containsKey(num)) {
                this.map.put(num, this.map.get(num) + 1);
            } else {
                if (this.isContained(result, num)) continue;
                this.map.put(num, 1);
            }
            if (this.map.get(num) > n) {
                result.add(num);
                this.map.remove(num);
            }
        }

        return result;
    }

    // 判断结果中是否已经包含了该数字
    public boolean isContained(List<Integer> result, int x) {
        return result.contains(x);
    }
}
